package com.cn.algorithm01;

import java.util.Arrays;

/**
 * @author hels
 * @version 1.0
 * @date 2021/10/11 18:05
 * 在有序数组中查询是否存在某个数
 */
public class Code03_Half {

    static int index = 1;

    // 生成随机数组
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int)((maxSize+1)*Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int)((maxValue+1)*Math.random());
        }
        return arr;
    }

    public static void main(String[] args) {
        int maxSize = 10, maxValue = 20;
        int times = 1000;
        boolean succeed = true;

        for (int i = 0; i < times; i++) {
            int[] arr = generateRandomArray(maxSize,maxValue);
            //保证有序
            Arrays.sort(arr);
            int num = (int)((maxValue+1)*Math.random());

            if(find(arr, num) != test(arr, num)){
                succeed = false;
            }
        }

        System.out.println(succeed ? "nice" : "fuck");

    }

    //在数组中找到num
    public static boolean find(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return false;
        }

        int L = 0, R = arr.length-1;
        while (L <= R) {
            int mid = (L + R)/2;
            if (arr[mid] == num) {
                //System.out.println((index++) + "个数字==" + arr[mid] + " : " + num);
                return true;
            } else if (arr[mid] < num) {
                L = mid + 1;
            } else if (arr[mid] > num) {
                R = mid - 1;
            }
        }
        return false;
    }

    //暴力破解
    public static boolean test(int[] arr, int num) {
        for (int n : arr) {
            if (n == num){
                return true;
            }
        }
        return false;
    }

}
